<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script>
            /*
            这题的重点：每个数只能用一次，且candidates中可能包含重复数字，结果可能重复  [1,7] [7,1]算重复
            这种写法会超时,所以需要进行优化

            */
            var combinationSum2 = function (candidates, target) {
                let map = new Map()
                let res = []
                function backTracking(path, startIndex, sum) {
                    if (sum > target) return
                    if (sum == target) {
                        let str = [...path].sort((a, b) => a - b).join('')
                        if (!map.has(str)) {
                            map.set(str, str)
                            res.push([...path])
                        }
                        return
                    }
                    for (let i = startIndex; i < candidates.length; i++) {
                        path.push(candidates[i])
                        backTracking(path, i + 1, sum + candidates[i])
                        path.pop()
                        //有个
                    }
                }
                backTracking([], 0, 0)
                return res
            }
            var combinationSum2 = function (candidates, target) {
                //直接对candidates先排序,每一层遍历如果当前元素和左邻元素相同就跳过，直至最后，有点类似于三数之和
                candidates.sort((a, b) => a - b)
                let path = []
                let res = []
                function backTracking(path, sum, startIndex) {
                    if (sum > target) return
                    if (sum == target) {
                        return res.push([...path])
                    }
                    for (let i = startIndex; i < candidates.length; i++) {
                        //如  [1,1,1,1,1]，它每次必定会把第一个推入path，从第二个判断与前一个是否相同
                        /* 
                        第一层 startIndex:0      1    1  1  1  1 
                        第二层 startIndex:1    1 1 1 1
                        */
                        if (i - 1 >= startIndex && candidates[i] == candidates[i - 1]) {
                            continue
                        }
                        path.push(candidates[i])
                        backTracking(path, sum + candidates[i], i + 1)
                        path.pop()
                    }
                }
                backTracking(path, 0, 0)
                return res
            }
        </script>
    </body>
</html>
